package demo3;

import java.util.*;

public class Solution {
    //1.找不同(哈希表)
    public char findTheDifference(String s, String t) {
        //哈希表计数
        Map<Character, Integer> hash = new HashMap<>();
        //计数
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        //对比
        for(int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);
            if(hash.containsKey(ch)){
                hash.put(ch, hash.get(ch) - 1);
                if(hash.get(ch) < 0){
                    return ch;
                }
            }else{
                return ch;
            }
        }
        return '-';
    }
    //1.找不同(哈希究极炫技法)
/*    public char findTheDifference(String s, String t) {
        //哈希究极炫技法
        int[] count = new int[26];//26个字母
        for(char ch : s.toCharArray()){
            count[ch - 'a']++;
        }
        for(char ch : t.toCharArray()){
            count[ch - 'a']--;
            if(count[ch - 'a'] < 0){
                return ch;
            }
        }
        return ' ';
    }*/
    //2.面试题 01.02. 判定是否互为字符重排(哈希炫技法)
    public boolean CheckPermutation(String s1, String s2) {
        //哈希炫技法
        int[] count = new int[26];
        for(char ch : s1.toCharArray()){
            count[ch - 'a']++;
        }
        for(char ch : s2.toCharArray()){
            count[ch - 'a']--;
            if(count[ch - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
    //3.反转字符串中的单词
    public String reverseWords(String s) {
        List<StringBuilder> list = new ArrayList<>();
        int index = -1;//list的下标
        //遍历，分成一个个单词
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != ' '){
                if(i - 1 < 0 || s.charAt(i - 1) == ' '){
                    list.add(new StringBuilder());
                    index++;
                }
                list.get(index).append(s.charAt(i));
            }
        }
        reverse(list, 0, index);
        //放入到ret中
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i <= index; i++){
            ret.append(list.get(i));
            if(i != index){
                ret.append(" ");
            }
        }
        return ret.toString();
    }
    private void reverse(List<StringBuilder> list, int start, int end){
        while(start < end){
            StringBuilder tmp = list.get(start);
            list.set(start, list.get(end));
            list.set(end, tmp);
            start++;
            end--;
        }
    }
    //4.面试题 01.06. 字符串压缩
    public String compressString(String S) {
        StringBuilder ret = new StringBuilder();
        int sum = 0;//总数
        int count = 1;//计数
        for(int i = 0; i < S.length(); i++){
            if(i < S.length() - 1 && S.charAt(i) == S.charAt(i + 1)){
                count++;
            }else{
                ret.append(S.charAt(i));
                ret.append(count);
                count = 1;
            }
        }
        return S.length() > ret.length() ? ret.toString() : S;
    }
    //5.找到字符串中所有字母异位词(滑动窗口)
    public List<Integer> findAnagrams(String s, String p) {
        //滑动窗口
        int sLen = s.length();
        int pLen = p.length();
        if(sLen < pLen){
            return (new ArrayList<>());
        }
        //返回顺序表
        List<Integer> ret = new ArrayList<>();
        //记录词频的窗口
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //放入一组做对比
        for(int i = 0; i < pLen; i++){
            ++pCount[p.charAt(i) - 'a'];
            ++sCount[s.charAt(i) - 'a'];
        }
        //放入了第一组，就先对比一下第一组
        if(Arrays.equals(sCount, pCount)){
            ret.add(0);
        }
        //开始滑动窗口
        for(int i = 0; i < sLen - pLen; i++){
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];
            if(Arrays.equals(sCount, pCount)){
                ret.add(i + 1);
            }
        }
        return ret;
    }
    //6.字符串相乘(模拟竖式计算)
    public String multiply(String num1, String num2) {
        //进行竖式计算
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        //始终让num1最长
        if(num1.length() < num2.length()){
            return multiply(num2, num1);
        }
        String str = "0";
        int count = 0;//计数器(关于后面加几个0的问题)
        //让num2的每一位与num1相乘
        for(int i = num1.length() - 1; i >= 0; i--){
            StringBuilder tmp = new StringBuilder();
            int ans = 0;//进位
            char ch1 = num1.charAt(i);
            for(int j = num2.length() - 1; j >= 0; j--){
                char ch2 = num2.charAt(j);
                int sum = (ch1 - '0') * (ch2 - '0') + ans;
                ans = sum / 10;
                sum %= 10;
                tmp.append(sum);
            }
            if(ans != 0){
                tmp.append(ans % 10);
            }
            tmp.reverse();
            //后面补0
            for(int k = 0; k < count; k++){
                tmp.append(0);
            }
            str = addStrings(str, tmp.toString());
            count++;
        }
        return str;
    }
    public String addStrings(String num1, String num2) {
        StringBuilder ret = new StringBuilder();
        int add = 0;//进位
        int sum = 0;//当前竖列的和
        //双指针模拟竖式计算
        char ch1 = 0;
        char ch2 = 0;
        for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0; i--, j--){
            if(i >= 0 && j >= 0){
                ch1 = num1.charAt(i);
                ch2 = num2.charAt(j);
            }else if(i < 0){
                ch1 = '0';
                ch2 = num2.charAt(j);
            }else{
                ch1 = num1.charAt(i);
                ch2 = '0';
            }
            sum = ch1 + ch2 - 2*'0' + add;
            if(sum >= 10){
                add = sum / 10;
            }else{//重置add
                add = 0;
            }
            ret.append(sum % 10);
        }
        if(add != 0){
            ret.append(add);
        }
        return ret.reverse().toString();
    }
    //7.剑指 Offer 48. 最长不含重复字符的子字符串(滑动窗口+哈希表)
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口+哈希表
        Set<Character> hash = new HashSet<>();
        int max = 0;
        for(int l = 0, r = 0; r < s.length(); r++){
            //如果包含，则去掉
            while(hash.contains(s.charAt(r))){
                hash.remove(s.charAt(l++));
            }
            hash.add(s.charAt(r));
            max = Math.max(max, hash.size());
        }
        return max;
    }
    //8.删除字符串中的所有相邻重复项(栈)
    public String removeDuplicates(String s) {
        //栈：倒着放入栈中，遇到相邻的重复项，则出栈
        Stack<Character> stack = new Stack<>();
        for(int i = s.length() - 1; i >= 0; i--){
            char ch = s.charAt(i);
            if(!stack.empty() && stack.peek() == ch){
                stack.pop();
            }else{
                stack.push(ch);
            }
        }
        StringBuilder ret = new StringBuilder();
        //放入ret中
        while(!stack.empty()){
            ret.append(stack.pop());
        }
        return ret.toString();
    }
    //9.同构字符串(哈希表)
    public boolean isIsomorphic(String s, String t) {
        //哈希表,建立s,t之间的映射关系
        Map<Character, Character> hash = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char cs = s.charAt(i);
            char ct = t.charAt(i);
            if(hash.containsKey(cs) || hash.containsValue(ct)){
                if(!hash.containsKey(cs)){
                    return false;
                }else if(hash.get(cs) != ct){
                    return false;
                }
            }
            hash.put(cs,ct);
        }
        return true;
    }
    //10.面试题 01.03. URL化
    public String replaceSpaces(String S, int length) {
        //转移
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < length; i++){
            char ch = S.charAt(i);
            if(ch != ' '){
                ret.append(ch);
            }else{
                ret.append("%20");
            }
        }
        return ret.toString();
    }
}
